package 分治;

import java.util.List;

/**
 * 148. 排序链表
 *
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 *
 * 解题思路：使用归并排序思路，将链表分为两部分进行排序，然后再合并，整个过程时递归的。
 *
 * 解题：
 *  1：归并排序：最优解时归并排序，时间复杂度时O(nlogn),空间复杂度为O(1)。
 *  2：递归步骤：
 *      分割链表：通过快慢指针找到链表的中点，分割为两部分
 *      递归排序：递归地对分割后的子链表进行排序
 *      合并有序链表：将排序后的子链表合并为一个有序数组。
 *
 */
public class L_148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        // 找到链表的中点
        ListNode mid = getMid(head);
        // 分割链表
        ListNode rightHead = mid.next;
        mid.next = null;

        // 递归排序左右两个子链表
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        return merge(left,right);
    }

    // 通过快慢指针法找到链表的中点
    private ListNode getMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 合并两个有序链表
    private ListNode merge(ListNode left, ListNode right){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (left!=null && right!=null){
            if (left.val < right.val){
                cur.next = left;
                left = left.next;
            }else {
                cur.next = right;
                right = right.next;
            }
            // 移动指针,排序下一个
            cur = cur.next;
        }
        // 将剩余部分的链表直接拼接
        if (left!=null){
            cur.next = left;
        }
        if (right!=null){
            cur.next = right;
        }
        return dummy.next;
    }

     public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
